using System;
using System.Diagnostics;
using Fine.Collections.Intf;
using Fine.Collections.Views;
using JetBrains.Annotations;



namespace Fine.Collections.Cont
{
    /// <summary>
    /// A map that keeps the order of K->V pairs,
    /// and with index-based access to this pairs.
    /// This map preserves the order in wich key-value pairs are added.
    /// </summary>
    /// <remarks>
    /// Note: removing non-last pair from this array can be a hard operation.
    /// </remarks>
    /// <typeparam name="K">key type.</typeparam>
    /// <typeparam name="V">values type.</typeparam>
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(ArrMap<,>.DebugView))]
    public class ArrMap<K, V> : WMap<K,V>
    {

        /// <summary>
        /// Storage of key-value pairs.
        /// </summary>
        [NotNull]
        private readonly ArrList<MapEntry<K,V>> entries;

        /// <summary>
        /// Hash map - created if count of items more than <see cref="UseHashTableThreasold"/>.
        /// </summary>
        [CanBeNull]
        private HashMap<K,int> hashMap;

        /// <summary>
        /// Keys view.
        /// </summary>
        private readonly RSet<K> keys;

        /// <summary>
        /// Values view.
        /// </summary>
        private readonly RRandomList<V> values;

        
        /// <summary>
        /// Count of pairs in the array when a hash table is created (if not yet).
        /// </summary>
        private const int UseHashTableThreasold = 7;

        /// <summary>
        /// Count of pairs in the array when a hash tables is dropped (if exists).
        /// </summary>
        private const int UnuseHashTableThreasold = 3;

        /// <summary>
        /// Default intials storage capacity.
        /// </summary>
        private const int DefaultCapacity = 16;




        /// <summary>
        /// Constructs an empty array-based map.
        /// </summary>
        public ArrMap() 
            // ReSharper disable RedundantArgumentDefaultValue
            : this(firstIndex: 1, initialCapacity: DefaultCapacity) 
            // ReSharper restore RedundantArgumentDefaultValue
        {}


        /// <summary>
        /// Constructs an empty array-based map with the specified capacity.
        /// </summary>
        /// <param name="firstIndex">origin index (index of the first item).</param>
        /// <param name="initialCapacity">initial capacity.</param>
        public ArrMap(int firstIndex = 1, int initialCapacity = DefaultCapacity)
        {
            entries = new ArrList<MapEntry<K,V>>(firstIndex, initialCapacity);
            keys = new KeysView(this);
            values = new RRandomListAdaptor<ArrList<MapEntry<K,V>>,MapEntry<K,V>,V>(entries, e => e.Value);
        }


        public RSet<K> Keys
        {
            get { return keys; }
        }


        /// <summary>
        /// Values as a random-accessible list.
        /// Values are holded in order of how their were added.
        /// </summary>
        public RRandomList<V> Values
        {
            get { return values; }
        }


        RCollection<V> RMap<K,V>.Values
        {
            get { return values; }
        }


        /// <summary>
        /// Entries as a random-accessible list.
        /// Entries are holded in order of how their were added.
        /// </summary>
        public RRandomList<RMapEntry<K,V>> Entries
        {
            get { return entries; }
        }


        RCollection<RMapEntry<K,V>> RMap<K,V>.Entries
        {
            get { return entries; }
        }


        public void Include(K key, V value)
        {
            if (ContainsKey(key))
                throw new DuplicatesFoundException("The key \"" + key + "\" already exists in the map.");

            entries.AddItem(new MapEntry<K, V>(key,value));

            if (hashMap == null)
            {
                if (entries.count >= UseHashTableThreasold)
                    BuildHashTable();
            }
            else
            {
                hashMap.Include(key, entries.lastIndex);
            }
        }

        private void BuildHashTable()
        {
            hashMap = new HashMap<K, int>();
            for (int i = entries.firstIndex; i <= entries.lastIndex; i++)
                hashMap.Include(entries[i].Key, i);
        }


        public V Exclude(K key)
        {
            int index = FindKey(key);
            if (index == int.MinValue) return default(V);

            V value = entries[index].Value;
            entries.RemoveElementAt(index);

            if (hashMap != null)
            {
                if (entries.count <= UnuseHashTableThreasold)
                {
                    hashMap = null;
                }
                else
                {
                    hashMap.Exclude(key);

                    // todo reimplement using LinkedListImp.ProcessAll
                    for (int j = index; j <= entries.lastIndex; j++)
                    {
                        K theKey = entries[j].Key;
                        hashMap[theKey] = j;
                    }
                }
            }

            return value;
        }


        public void Clear()
        {
            entries.Clear();
            hashMap = null;
        }


        V RMap<K,V>.this[K key]
        {
            get
            {
                return Find(key).Item;
            }
        }


        public V this[K key]
        {
            get 
            { 
                return Find(key).Item; 
            }

            set
            {
                int index = FindKey(key);
                if (index == int.MinValue)
                    Include(key, value);
                else
                    entries.ar[index - entries.firstIndex].Value = value;
            }
        }

        
        
        public int Count
        {
            get { return entries.Count; }
        }

        public bool IsEmpty
        {
            get { return entries.IsEmpty; }
        }

        public bool IsNotEmpty
        {
            get { return entries.IsNotEmpty; }
        }

        public int FirstIndex
        {
            get { return entries.FirstIndex; }
        }

        public int LastIndex
        {
            get { return entries.LastIndex; }
        }


        /// <summary>
        /// Represents a quick read-only indexed access to the map.
        /// </summary>
        /// <remarks>
        /// The given index must be in [ <c>FirstIndex</c> .. <c>LastIndex</c> ] inclusive.
        /// </remarks>
        /// <param name="index">index of pair to access.</param>
        /// <exception cref="CollectionIsEmptyException">when the collection is empty.</exception>
        /// <exception cref="IndexOutOfBoundsException">when index is incorrect.</exception>
        /// <seealso cref="RRandomList{T}.FirstIndex"/>
        /// <seealso cref="RRandomList{T}.LastIndex"/>
        public RMapEntry<K,V> this[int index]
        {
            get 
            {           
                int intIndex = entries.CalcInternalIndex(index);
                return entries.ar[intIndex];
            }
        }


        public bool ContainsKey(K key)
        {
            if (hashMap != null)
            {
                return hashMap.ContainsKey(key);
            }
            else
            {        
                for (int i = 0; i < entries.count; i++)
                    if (entries.ar[i].Key.Equals(key))
                        return true;
                return false;
            }
        }


        /// <summary>
        /// Looks for the specified key in the map,
        /// and returns an index of this key.
        /// </summary>
        /// <param name="key">key to look for.</param>
        /// <returns>index of the key, or <c>int.MinValue</c> if not found.</returns>
        public int FindKey(K key)
        {
            if (hashMap != null)
            {
                var result = hashMap.Find(key);
                return result.Found ? result.Item : int.MinValue;
            }
            else
            {
                for (int i = 0; i < entries.count; i++)
                    if (entries.ar[i].Key.Equals(key))
                        return entries.firstIndex + i;
                return int.MinValue;
            }
        }


        /// <summary>
        /// Looks for the pair with the specified key.
        /// </summary>
        /// <param name="key">key to look for.</param>
        /// <returns>the associated value if found.</returns>
        public SearchResult<V> Find(K key)
        {
            if (hashMap != null)
            {
                var result = hashMap.Find(key);
                return result.Found 
                        ? SearchResults<V>.Found(entries[result.Item].Value) 
                        : SearchResults<V>.NotFound();
            }
            else
            {
                for (int i = 0; i < entries.count; i++)
                    if (entries.ar[i].Key.Equals(key))
                        return SearchResults<V>.Found(entries.ar[i].Value);
                return SearchResults<V>.NotFound();
            }
        }


        #region KEYS VIEW

        private sealed class KeysView : RCollectionAdaptor<ArrList<MapEntry<K,V>>,MapEntry<K,V>,K>,
                                        RSet<K>
        {
            private readonly ArrMap<K,V> map;

            internal KeysView(ArrMap<K,V> map)
                : base(map.entries, e => e.Key)
            {
                this.map = map;
            }


            public bool Contains(K item)
            {
                return map.ContainsKey(item);
            }
        }

        #endregion



        #region DEBUG HELPER

        /// <summary>
        /// Debug helper.
        /// </summary>
        internal class DebugView
        {
            private readonly ArrList<MapEntry<K,V>> entries;


            public DebugView(ArrMap<K,V> map)
            {
                this.entries = map.entries;
            }


            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public Array Items
            {
                get
                {
                    return DebugViewUtils.MakeArray(entries.ar, entries.firstIndex, entries.count); 
                }
            }
        }

        #endregion

    }
}